import itertools
from .datastruct import Quene as _Quene, Stack as _Stack
from ..math.mathematic import inf as _inf
from numpy import ndarray as _ndarray, zeros as _zeros
__all__ = [
    "idGen",
    "Edge",
    "EdgeSet",
    "Vertex",
    "Graph",
    "Node",
    "Tree",
]


def idGen():
    temp = 0
    while 1:
        yield temp
        temp += 1


class Edge:
    """边"""

    def __init__(self, tail: str, head: str, val: float = 1.0) -> None:
        self.tail: str = tail
        self.head: str = head
        self.val: float = val

    def __neg__(self):
        return Edge(self.head, self.tail, self.val)

    def __str__(self):
        return f"{self.tail} - {self.val} -> {self.head}"

    def __repr__(self) -> str:
        temp = f"Edge({repr(self.tail)}, {repr(self.head)},"
        if self.val != 1.0:
            temp += f" {self.val}"
        return f"{temp})"

    def isLoop(self) -> bool:
        """是否为环"""
        return self.tail == self.head

    def __int__(self):
        return int(self.val)

    def __float__(self):
        return float(self.val)

    def __eq__(self, other):
        return self.tail == other.tail and self.head == other.head

    def __lt__(self, other):
        return False if other is None else self.val < float(other)

    def __gt__(self, other):
        return False if other is None else self.val > float(other)

    def __hash__(self):
        return hash((self.tail, self.head))


class EdgeSet:
    """边集"""

    def __init__(self, *initdata) -> None:
        self.edges: set[Edge] = set(initdata)

    def add(self, edge: Edge) -> None:
        """增加边"""
        if temp := self.exist(edge):
            self.edges.remove(temp)
        self.edges.add(edge)

    def remove(self, edge: Edge):
        """删除边"""
        todo = [edg for edg in self.edges if edg == edge]
        [self.edges.remove(edg) for edg in todo]

    def exist(self, edge: Edge) -> bool:
        """存在边"""
        return next((edg for edg in self.edges if edg == edge), False)

    def __iter__(self):
        yield from self.edges

    def __len__(self):
        return len(self.edges)

    def __set__(self):
        return self.edges

    def __add__(self, other):
        temp = EdgeSet()
        temp.edges = set(self) | set(other)
        return temp

    def __repr__(self) -> str:
        temp = "EdgeSet(\n"
        for edge in self.edges:
            temp += f"{repr(edge)},\n"
        return f'{temp})'


class Vertex:
    """节点"""

    def __init__(self, tag: str) -> None:
        self.tag: str = tag
        self.outs: EdgeSet = EdgeSet()
        self.ins: EdgeSet = EdgeSet()

    def __str__(self):
        temp = ''
        temp += f"{len(self.ins)} -> " if self.ins else ''
        temp += repr(self)
        temp += f" -> {len(self.outs)}" if self.outs else ''
        return temp

    def __neg__(self):
        vertex = Vertex(self.tag)
        for edge in self.ins:
            vertex.outs.add(-edge)
        for edge in self.outs:
            vertex.ins.add(-edge)
        return vertex

    def __repr__(self) -> str:
        return f"Vertex({repr(self.tag)})"

    def degree(self): return len(self.ins)+len(self.outs)
    __len__ = degree

    def neighborhood(self):
        """邻域"""
        for edge in self.outs:
            if edge.head != self.tag:
                yield edge.head


class Graph:
    """图"""

    def __init__(self) -> None:
        self.vertexs: list[Vertex] = []
        self.edges: EdgeSet = EdgeSet()
        self.tags: dict[str, int] = {}

    def __len__(self):
        return len(self.vertexs)

    def __str__(self) -> str:
        return f"Graph({len(self)} Vertex, {len(self.edges)} Edge)"

    def __neg__(self):
        """反图"""
        graph = Graph()
        for vertex in self.vertexs:
            graph.addVertex(vertex.tag)
        for edge in self.edges:
            graph.__addEdge(-edge)
        return graph

    def addVertex(self, tag: str) -> None:
        """增加一个节点"""
        tag = tag
        self.tags[tag] = len(self)
        self.vertexs.append(Vertex(tag))

    def addVertexs(self, tags: list) -> None:
        """增加多个节点"""
        for tag in tags:
            self.addVertex(tag)

    def delVertex(self, tag: str) -> None:
        """删除一个节点"""
        ifr = self.tags[tag]
        for edge in self.vertexs[ifr].ins+self.vertexs[ifr].outs:
            self.__delEdge(edge)
        for vertex in self.vertexs[ifr+1:]:
            self.tags[vertex.tag] -= 1
        del self.vertexs[ifr]
        del self.tags[tag]

    def __addEdge(self, edge: Edge) -> None:
        ifr, ito = self.tags[edge.tail], self.tags[edge.head]
        self.vertexs[ifr].outs.add(edge)
        self.vertexs[ito].ins.add(edge)
        self.edges.add(edge)

    def addEdge(self, fr: str, to: str, val=1.0) -> None:
        """增加一条边"""
        if not self.existVertex(fr):
            self.addVertex(fr)
        if not self.existVertex(to):
            self.addVertex(to)
        self.__addEdge(Edge(fr, to, val))

    def __delEdge(self, edge: Edge) -> None:
        ifr, ito = self.tags[edge.tail], self.tags[edge.head]
        self.vertexs[ifr].outs.remove(edge)
        self.vertexs[ito].ins.remove(edge)
        self.edges.remove(edge)

    def delEdge(self, fr: str, to: str) -> None:
        """删除一条边"""
        self.__delEdge(Edge(fr, to))

    def addEdge_Undirected(self, fr: str, to: str, val=1.0) -> None:
        """增加一条无向边"""
        self.addEdge(fr, to, val)
        self.addEdge(to, fr, val)

    def getEdge(self, fr: str, to: str) -> Edge:
        temp = Edge(fr, to, 0)
        for edge in self.edges:
            if edge == temp:
                return edge
        return temp

    def getVertex(self, tag: str) -> Vertex:
        return self.vertexs[self.tags[tag]]

    def genCheckTable(self) -> dict:
        return {i: False for i in self.tags}

    def DFS(self, tag: str) -> Vertex:
        """深度优先搜索"""
        visit = self.genCheckTable()
        todo = _Stack([tag])
        while todo:
            yield (tag := todo.pop())
            for tag in self.getVertex(tag).neighborhood():
                if not visit[tag]:
                    visit[tag] = True
                    todo.push(tag)

    def BFS(self, tag: str) -> Vertex:
        """宽度优先搜索"""
        visit = self.genCheckTable()
        todo = _Quene([tag])
        while todo:
            yield (tag := todo.pop())
            for tag in self.getVertex(tag).neighborhood():
                if not visit[tag]:
                    visit[tag] = True
                    todo.push(tag)

    transpose = __neg__

    def existVertex(self, tag: str) -> bool:
        """存在节点"""
        temp = self.tags.get(tag, None)
        return temp is not None

    def copy(self):
        """获取一份拷贝"""
        graph = Graph()
        for vertex in self.vertexs:
            graph.addVertex(vertex.tag)
        for edge in self.edges:
            graph.__addEdge(edge)
        return graph

    def toposort(self):
        """Kahn算法拓扑排序"""
        graph = self.copy()
        s = {vertex for vertex in self.vertexs if not vertex.ins}
        l: list[Vertex] = []
        while s:
            vertex: Vertex = s.pop()
            l.append(vertex)
            for edge in vertex.outs:
                edge: Edge
                head = graph.tags[edge.head]
                graph.vertexs[head].ins.remove(edge)
                graph.edges.remove(edge)
                if not graph.getVertex(edge.head).ins:
                    s.add(graph.getVertex(edge.head))
        if graph.edges:
            raise Exception("Graph has loop.")
        return l

    def matrix(self) -> _ndarray:
        """生成邻接矩阵"""
        mtx = _zeros((len(self), len(self)), dtype="float64")
        mtx += _inf
        for edge in self.edges:
            mtx[self.tags[edge.tail]][self.tags[edge.head]] = edge.val
        return mtx

    def genDistanceMatrix_Floyd(self) -> _ndarray:
        """Floyd最短路算法生成最短距离矩阵"""
        dis = self.matrix()
        lens = len(self)
        for k, i, j in itertools.product(range(lens), range(lens), range(lens)):
            dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
        return dis


class Node:
    """树节点"""

    def __init__(self, branch: int = 2) -> None:
        branch = max(branch, 2)
        self.childs: list[Node] = []*branch

    def __setitem__(self, index: int, value):
        self.childs[index] = value

    def left(self):
        return self.childs[0]

    def right(self):
        return self.childs[-1]


class Tree:
    """树"""

    def __init__(self, branch: int = 2) -> None:
        self.branch: int = branch
        self.root: Node = Node(branch)
